#include <iostream>
#include <queue>

using namespace std;

struct TreeNode
{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode()
		:val(0)
		, left(nullptr)
		, right(nullptr)
	{}
	TreeNode(int x)
		:val(x)
		, left(nullptr)
		, right(nullptr)
	{}
	TreeNode(int x, TreeNode* left, TreeNode* right)
		:val(x)
		, left(left)
		, right(right)
	{}
};

class Solution
{
public:
	bool isEvenOddTree(TreeNode* root)
	{
		int level = 0;
		TreeNode* cur = root;
		st.push(root);
		while (!st.empty())
		{
			int size = st.size();
			while (size)
			{
				TreeNode* cur = st.front();
				if ((cur->val % 2) == (level % 2))
				{
					return false;
				}
				st.pop();
				--size;
				if (size > 0)
				{
					if ((level % 2 == 1) && cur->val <= st.front()->val)
					{
						return false;
					}
					if ((level % 2 == 0) && cur->val >= st.front()->val)
					{
						return false;
					}
				}
				if (cur->left)
				{
					st.push(cur->left);
				}
				if (cur->right)
				{
					st.push(cur->right);
				}
			}

			++level;
		}
		return true;
	}
private:
	queue<TreeNode*> st;
};

int main()
{
	TreeNode* I = new TreeNode(6);
	TreeNode* G = new TreeNode(2);
	TreeNode* F = new TreeNode(12);
	TreeNode* H = new TreeNode(8);
	TreeNode* C = new TreeNode(3, F, H);
	TreeNode* D = new TreeNode(7, I, nullptr);
	TreeNode* E = new TreeNode(9, nullptr, G);
	TreeNode* A = new TreeNode(10, C, nullptr);
	TreeNode* B = new TreeNode(4, D, E);
	TreeNode* root = new TreeNode(1, A, B);

	/*TreeNode* C = new TreeNode(3);
	TreeNode* D = new TreeNode(3);
	TreeNode* A = new TreeNode(4, C, D);
	TreeNode* B = new TreeNode(2);
	TreeNode* root = new TreeNode(5, A, B);
	TreeNode* E = new TreeNode(7);
	B->left = E;*/

	/*TreeNode* E = new TreeNode(7);
	TreeNode* C = new TreeNode(3);
	TreeNode* D = new TreeNode(5);
	TreeNode* A = new TreeNode(9, C, D);
	TreeNode* B = new TreeNode(1, E, nullptr);
	TreeNode* root = new TreeNode(5, A, B);*/

	Solution xz;

	int n = xz.isEvenOddTree(root);
	cout << n << endl;
	return 0;
}
